package gold.enterprise;


class UF {
    int count;
    int[] parent;
    int[] rank;

    //由于本题目是二维的，构造函数需要特殊处理为二维矩阵的输入
    public UF(int[][] land) {
        count = 0;
        int m = land.length, n = land[0].length;
        parent = new int[m * n];    //parnet数组是二维点的总长度
        rank = new int[m * n];
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++i) {
                if (land[i][j] == 1) parent[i * n + j] = i * n + j;//默认父节点为自己
                ++count;    //统计"大陆"集团大小
                rank[i * n + j] = 0;
            }
        }
    }

    // find 函数实现
    public int find(int i) {
        if (parent[i] != i) parent[i] = find(parent[i]);//递归调用find直到终止条件如下：
        return parent[i];    //找到了最终集团原始父节点
    }


    // union 函数实现
    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            if (rank[rootX] > rank[rootY]) parent[rootY] = rootX;
            else parent[rootX] = rootY;

            --count;    //总集团数量减一
        }
    }
}

public class Banyu {
    public int findMaxNumOfIslands(int[][] land) {
        if (null == land || land[0].length == 0) return 0;//防御式编程
        int n = land.length, m = land[0].length;
        UF uf = new UF(land);

        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j) {
                if (land[i][j] == 0) continue;
                if (i - 1 >= 0 && land[i - 1][j] == 1) {
                    uf.union(i * n + j, (i - 1) * n + j);
                    continue;//只能并到一个集团中去
                }

                if (j - 1 >= 0 && land[i][j - 1] == 1) {
                    uf.union(i * n + j, (i) * n + j - 1);
                    continue;//只能并到一个集团中去
                }


                if (i + 1 < n && land[i + 1][j] == 1) {
                    uf.union(i * n + j, (i + 1) * n + j);
                    continue;//只能并到一个集团中去
                }

                if (j + 1 < n && land[i][j + 1] == 1) {
                    uf.union(i * n + j, (i) * n + j + 1);
                    continue;//只能并到一个集团中去
                }
            }

        int maxCountIsLand = 0;
        for (int i = 0; i < m * n; ++i) {
            maxCountIsLand = Math.max(maxCountIsLand, uf.rank[i]);
        }

        return maxCountIsLand;
    }
}










